package leetcode.code1026;

import leetcode.IDebug;
import leetcode.helper.tree.TreeNode;

public class Solution implements IDebug {

	public int maxAncestorDiff(TreeNode root) {
		if (root == null) {
			return 0;
		}
		return this.f(root)[2];
	}

	private int[] f(TreeNode root) {// [子树上的最小值,子树上的最大值，答案]
		int val = root.val;
		int min = val;
		int max = val;
		int ans = 0;
		if (root.left != null) {
			int[] info = this.f(root.left);
			min = Math.min(min, info[0]);
			max = Math.max(max, info[1]);
			ans = Math.max(info[2], Math.max(Math.abs(val - info[0]), Math.abs(val - info[1])));
		}
		if (root.right != null) {
			int[] info = this.f(root.right);
			min = Math.min(min, info[0]);
			max = Math.max(max, info[1]);
			// 之前可能有一个ans，需要参与比较
			ans = Math.max(Math.max(ans, info[2]), Math.max(Math.abs(val - info[0]), Math.abs(val - info[1])));
		}
		return new int[] { min, max, ans };
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		System.out.println(Math.abs(3 - 1));
		System.out.println(Math.abs(1 - 3));
	}

}
